class Solution {
    public boolean isPalindrome(String s) {
        if(s == null || s.length() == 0 ){return true;}

        char[] array =   s.toCharArray();
        int i = 0; int j = array.length - 1;

        while(i < j){
            char head = array[i];
            char tail = array[j];
            if(!Character.isLetterOrDigit(head)){ i++;continue;}
            if(!Character.isLetterOrDigit(tail)){ j–;continue;}

            if(Character.toLowerCase(head) !=  Character.toLowerCase(tail)){return false;}
            i++;
            j–;

        }
    return true;
    }
}

public class Solution {
      public static UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
          if(node == null){
              return node;
          }
      //get first node
      UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
      HashMap<Integer,UndirectedGraphNode> map = new HashMap<>();
      map.put(newNode.label, newNode);
      Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
      queue.offer(node);

      while(!queue.isEmpty()){
          UndirectedGraphNode temp = queue.poll();
          for(UndirectedGraphNode n : temp.neighbors){
              if(!map.containsKey(n.label)){
                  map.put(n.label, new UndirectedGraphNode(n.label));
                  queue.offer(n);
              }
              UndirectedGraphNode newN = map.get(n.label);
              map.get(temp.label).neighbors.add(newN);
          }
      }
    return newNode;
  }
}

public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums.length < 4) return result;
    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 3; ++i) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        for (int j = i + 1; j < nums.length - 2; ++j) {
            if (j > i+1 && nums[j] == nums[j-1]) continue;
            int k = j + 1;
            int l = nums.length - 1;
            while (k < l) {
                final int sum = nums[i] + nums[j] + nums[k] + nums[l];
                if (sum < target) {
                    ++k;
                    while(nums[k] == nums[k-1] && k < l) ++k;
                } else if (sum > target) {
                    –l;
                    while(nums[l] == nums[l+1] && k < l) –l;
                } else {
                    result.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
                    ++k;
                    –l;
                    while(nums[k] == nums[k-1] && k < l) ++k;
                    while(nums[l] == nums[l+1] && k < l) –l;
                }
            }
        }
    }
    return result;
}

public class Solution {
    int M = 1000000007;
    public int numDecodings(String s) {
        long first = 1, second = s.charAt(0) == '' ? 9 : s.charAt(0) == '0' ? 0 : 1;
        for (int i = 1; i < s.length(); i++) {
            long temp = second;
            if (s.charAt(i) == '') {
                second = 9  second;
                if (s.charAt(i - 1) == '1')
                    second = (second + 9  first) % M;
                else if (s.charAt(i - 1) == '2')
                    second = (second + 6  first) % M;
                else if (s.charAt(i - 1) == '')
                    second = (second + 15  first) % M;
            } else {
                second = s.charAt(i) != '0' ? second : 0;
                if (s.charAt(i - 1) == '1')
                    second = (second + first) % M;
                else if (s.charAt(i - 1) == '2' && s.charAt(i) <= '6')
                    second = (second + first) % M;
                else if (s.charAt(i - 1) == '')
                    second = (second + (s.charAt(i) <= '6' ? 2 : 1)  first) % M;
            }
            first = temp;
        }
        return (int) second;
    }

}   

public int maxProfit(int k, int[] prices) {
    // write your code here
    if (k == 0) {
        return 0;
    }
    if (k >= prices.length / 2) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }
    int n = prices.length;
    int[][] mustsell = new int[n + 1][n + 1];   // mustSell[i][j] 表示前i天，至多进行j次交易，第i天必须sell的最大获益
    int[][] globalbest = new int[n + 1][n + 1];  // globalbest[i][j] 表示前i天，至多进行j次交易，第i天可以不sell的最大获益

    mustsell[0][0] = globalbest[0][0] = 0;
    for (int i = 1; i <= k; i++) {
        mustsell[0][i] = globalbest[0][i] = 0;
    }

    for (int i = 1; i < n; i++) {
        int gainorlose = prices[i] - prices[i - 1];
        mustsell[i][0] = 0;
        for (int j = 1; j <= k; j++) {
            mustsell[i][j] = Math.max(globalbest[(i - 1)][j - 1] + gainorlose,
                                        mustsell[(i - 1)][j] + gainorlose);
            globalbest[i][j] = Math.max(globalbest[(i - 1)][j], mustsell[i ][j]);
        }
    }
    return globalbest[(n - 1)][k];
}

    public double pow(double x, int n) {
        if(n == 0)
            return 1;
        if(n<0){
            n = -n;
            x = 1/x;
        }
        return (n%2 == 0) ? pow(xx, n/2) : xpow(xx, n/2);
    }   

  public String addBinary(String a, String b) {
    int i = a.length() - 1;
    int j = b.length() - 1;
    String res = "";
    int add = 0;
    while(i >= 0 || j >= 0){
        int sum = add;  //进位：Carry
        sum += (i >= 0) ? a.charAt(i) - '0' : 0;
        sum += (j >= 0) ? b.charAt(j) - '0' : 0;
        res = (sum % 2) + res;
        add = sum / 2;
        i–;
        j–;
    }

   if( add > 0){
       res = add + res;
   }


    return res;
}

 //二分法 from 1 to x!
public int sqrt(int x) {
    // write your code here
    if(x == 0){
        return 0;
    }
    long start = 1 ; long end = x;
    while(start + 1 < end ){
        long mid = (start + end ) / 2;
        if( midmid < x){
            start = mid;
        }else if( midmid > x){
            end = mid;
        }else{
            return (int)mid;
        }
    }
    if( endend <= x){
        return (int) end;
    }else{
        return (int) start;
    }
}  

    // Contintuely miles divisor,  use bit computing to let divisors increase as multiply rate
    //时间复杂度O(logn)，空间复杂度O(1)
    public int divide(int dividend, int divisor) {
    if(divisor == 0){
        return Integer.MAX_VALUE;
    }

    if(dividend == 0) {return 0;}
    if(dividend == Integer.MIN_VALUE && divisor == -1) {return Integer.MAX_VALUE;}


    boolean isNeg = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);

    long a = Math.abs((long) dividend);
    long b = Math.abs((long) divisor);

    int res = 0;
    while( a >= b ){
        int shift = 0;
        while( a >= (b<<shift)){
            shift++;
        }
        a -= b<< (shift - 1 );
        res += 1 << (shift - 1);
    }
    return isNeg ? -res : res;
}   

public String countAndSay(int n) {
    String result = "1";
    int i = 1;
    while( i < n){
        StringBuilder sb = new StringBuilder();
        char [] array = result.toCharArray();
        for(int m = 0; m < array.length; m++){
            int count = 1;
            while( m < array.length - 1 && array[m] == array[m + 1]){
                count++;
                m++;
            }
            sb.append(count + String.valueOf(array[m]));
        }
        result = sb.toString();

        i++;
    }
    return result;
}  

 // Current[ String length] -  At that Character[string length] >= k

  public static String getStr(String s, int k) {
  Map<Character, Integer> map = new HashMap<Character, Integer>();
  StringBuilder sb = new StringBuilder();

  for (char c : s.toCharArray()) {
    int idx = map.getOrDefault(c, -k);

    while(sb.length() - k < idx) {
      sb.append("_");
    }
    sb.append(c);
    map.put(c,sb.length());
  }
  return sb.toString();
}  

//Ans = idle_slots+TotalNumberOfTasks
//we can observe that the maximum number of idle slots will always be given by the product of the cooling time and the number of instances of the task with maximum count less 1
//
法1 public int leastInterval(char[] tasks, int n) {
    int[] map = new int[26];
    for (char c: tasks)
        map[c - 'A']++;
    Arrays.sort(map);
    int max_val = map[25] - 1, idle_slots = max_val  n;
    for (int i = 24; i >= 0 && map[i] > 0; i–) {
        idle_slots -= Math.min(map[i], max_val);
    }
    return idle_slots > 0 ? idle_slots + tasks.length : tasks.length;
}

    法2  public int leastInterval(char[] tasks, int n) {
       //priority - quenue?
        int map[] = new int[26];
        for(char c : tasks){
            map[c - 'A']++;
        }
        PriorityQueue <Integer> queue = new PriorityQueue<>(26,
         Collections.reverseOrder());

        for(int i : map){
            if(i != 0)
                queue.add(i);
        }
        int times = 0;
        while(!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            int i = 0;
            while( i <= n ){
                if(!queue.isEmpty()){
                    if(queue.peek() > 1){
                        list.add(queue.poll() - 1);
                    }else{
                        queue.poll();
                    }
                }
                times++;
                if(queue.isEmpty() && list.size() == 0)
                    break;
                i++;
            }
            for(int l : list){
                    queue.offer(l);
                }
        }

        return times;
    }     

 ArrayList<ArrayList<String>> solveNQueens(int n) {
    // write your code here
     ArrayList<ArrayList<String>> result  = new ArrayList<>();
     if(n <= 0){
         return result;
     }

     search(result, new ArrayList<Integer>(), n);
     return result;
}


public void search( ArrayList<ArrayList<String>> result, ArrayList< Integer> cols, int n){
    if(cols.size() == n){
        result.add(drawChessboard(cols));
        return;
    }

    for(int colIndex = 0 ; colIndex < n ; colIndex++){
        if(!isValid(cols, colIndex) ){
            continue;
        }
        cols.add(colIndex);
        search(result,cols,n);
        cols.remove(cols.size() - 1);
    }
}

public boolean isValid(ArrayList<Integer> cols, int column){
    int row = cols.size();
    //i is rowIndex;
    for( int i = 0; i < cols.size(); i++ ){
        if(cols.get(i) == column ){
            return false;
        }

        if( i + cols.get(i) == row + column){
            return false;
        }
        if( i - cols.get(i) == row - column){
            return false;
        }
    }
    return true;
}


public ArrayList<String> drawChessboard(ArrayList<Integer> cols ){
     ArrayList<String> chess = new ArrayList<>();
     for(int i = 0; i < cols.size(); i++ ){
         StringBuilder sb = new StringBuilder();
         for(int j = 0; j< cols.size(); j++){
             //这里cols.get(i) 不是j
             sb.append( j == cols.get(i) ? 'Q':'.' );
         }
         chess.add(sb.toString());
     }
     return chess;
}

     public int minDistance(String word1, String word2) {
    int n = word1.length();
    int m = word2.length();
    int[][]nums = new int[n+1][m+1];

    for(int i = 0; i <= n ;i++){
        nums[i][0] = i;
    }
    for(int j = 0; j <=m; j++){
        nums[0][j] = j;
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <=m; j++){
            if( word1.charAt(i - 1) == word2.charAt(j - 1)){
                 nums[i][j] = nums[i - 1][j - 1];
            }else{
                nums[i][j] = Math.min(Math.min(nums[i-1][j] ,nums[i][j-1]),nums[i-1][j-1]) + 1;
            }
        }
    }

    return nums[n][m];
}   

public boolean isOneEditDistance(String s, String t) {
        // Write your code here
        if (s.length() > t.length()) {
            return isOneEditDistance(t, s);
        }
        int diff = t.length() - s.length();

        if (diff > 1) {
            return false;
        }
        if (diff == 0) {
            int cnt = 0;
            for (int i = 0; i < s.length(); i++) {
                if (t.charAt(i) != s.charAt(i)) {
                    cnt++;
                }
            }
            return (cnt == 1);
        }
        if (diff == 1) {
            for (int i = 0; i < s.length(); i++) {
                if (t.charAt(i) != s.charAt(i)) {
                    return (s.substring(i).equals(t.substring(i + 1)));
                }
            }
        }
        return true;
    }   

    public void sortColors(int[] nums) {
    // write your code here
    int i = 0;
    int j = nums.length - 1;
    int a = 0;
    while( a <= j){//这里一定是有等号的
        if(nums[a] == 0){
            swap(nums, a , i);
            i++;
            a++;
        }else if( nums[a] == 2){
            swap(nums, a, j);
            j–;
        }else{
            a++;
        }

    }
}

//K 个： counting
    public  void sortColors2(int[] colors, int k) {
    int[] count = new int[k+1];

    for (int i = 0; i < colors.length; i++){
        count[colors[i]]++;
    }

    int index = 0;
    for (int i = 1; i < count.length;i++){
        while (count[i]>0){
            colors[index] = i;
            index++;
            count[i]–;
        }
    }
}

//O(nlogk) Recursion
    public void sortColors2(int[] colors, int k) {
    if (colors == null || colors.length == 0) {
        return;
    }
    rainbowSort(colors, 0, colors.length - 1, 1, k);
}

public void rainbowSort(int[] colors,
                        int left,
                        int right,
                        int colorFrom,
                        int colorTo) {
    if (colorFrom == colorTo) {
        return;
    }

    if (left >= right) {
        return;
    }

    int colorMid = (colorFrom + colorTo) / 2;
    int l = left, r = right;
    while (l <= r) {
        while (l <= r && colors[l] <= colorMid) {
            l++;
        }
        while (l <= r && colors[r] > colorMid) {
            r–;
        }
        if (l <= r) {
            int temp = colors[l];
            colors[l] = colors[r];
            colors[r] = temp;

            l++;
            r–;
        }
    }

    rainbowSort(colors, left, r, colorFrom, colorMid);
    rainbowSort(colors, l, right, colorMid + 1, colorTo);
}

    public boolean wordBreak(String s, Set<String> dict) {
    // write your code here

     boolean[] f = new boolean[s.length() + 1];

    f[0] = true;

    for(int i=1; i <= s.length(); i++){
        for(int j=0; j < i; j++){
            if(f[j] && dict.contains(s.substring(j, i))){
                f[i] = true;
                break;
            }
        }
    }

    return f[s.length()];
}

    public ArrayList<String> wordBreak(String s, Set<String> dict) {
    // Note: The Solution object is instantiated only once and is reused by each test case.
    Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
    return wordBreakHelper(s,dict,map);
}

public ArrayList<String> wordBreakHelper(String s, Set<String> dict, Map<String, ArrayList<String>> memo){
    if(memo.containsKey(s)) return memo.get(s);
    ArrayList<String> result = new ArrayList<String>();
    int n = s.length();
    if(n <= 0) return result;
    for(int len = 1; len <= n; ++len){
        String subfix = s.substring(0,len);
        if(dict.contains(subfix)){
            if(len == n){
                result.add(subfix);
            }else{
                String prefix = s.substring(len);
                ArrayList<String> tmp = wordBreakHelper(prefix, dict, memo);
                for(String item:tmp){
                    item = subfix + " " + item;
                    result.add(item);
                }
            }
        }
    }
    memo.put(s, result);
    return result;
}  

private int ans = 0;

public int wordBreak3(String s, Set<String> dict) {
    int n = s.length();
    String lowerS = s.toLowerCase();

    Set<String> lowerDict = new HashSet<String>();
    for(String str : dict) {
        lowerDict.add(str.toLowerCase());
    }

    wordBreakhelper(lowerS, lowerDict, 0, n);
    return ans;
}

public void wordBreakhelper(String s,
                            Set<String> dict,
                            int start,
                            int len) {
    if (start == len) {
        ans++;
    }

    for(int i = start; i < len; i++) {
        String substr = s.substring(start, i + 1);
        if (dict.contains(substr)) {
           wordBreakhelper(s, dict, i + 1, len);
        }
    }
}  

public boolean canFinish(int numCourses, int[][] prerequisites) {
    // Write your code here
    List[] edges = new ArrayList[numCourses];
    int[] degree = new int[numCourses];

    for (int i = 0;i < numCourses; i++)
        edges[i] = new ArrayList<Integer>();

    for (int i = 0; i < prerequisites.length; i++) {
        degree[prerequisites[i][0]] ++ ;
        edges[prerequisites[i][1]].add(prerequisites[i][0]);
    }

    Queue queue = new LinkedList();
    for(int i = 0; i < degree.length; i++){
        if (degree[i] == 0) {
            queue.add(i);
        }
    }

    int count = 0;
    while(!queue.isEmpty()){
        int course = (int)queue.poll();
        count ++;
        int n = edges[course].size();
        for(int i = 0; i < n; i++){
            int pointer = (int)edges[course].get(i);
            degree[pointer]–;
            if (degree[pointer] == 0) {
                queue.add(pointer);
            }
        }
    }

    return count == numCourses;
}      

public int[] findOrder(int numCourses, int[][] prerequisites) {
    // Write your code here
    List[] edges = new ArrayList[numCourses];
    int[] degree = new int[numCourses];

    for (int i = 0;i < numCourses; i++)
        edges[i] = new ArrayList<Integer>();

    for (int i = 0; i < prerequisites.length; i++) {
        degree[prerequisites[i][0]] ++ ;
        edges[prerequisites[i][1]].add(prerequisites[i][0]);
    }

    Queue queue = new LinkedList();
    for(int i = 0; i < degree.length; i++){
        if (degree[i] == 0) {
            queue.add(i);
        }
    }

    int count = 0;
    int[] order = new int[numCourses];
    while(!queue.isEmpty()){
        int course = (int)queue.poll();
        order[count] = course;
        count ++;
        int n = edges[course].size();
        for(int i = n - 1; i >= 0 ; i–){
            int pointer = (int)edges[course].get(i);
            degree[pointer]–;
            if (degree[pointer] == 0) {
                queue.add(pointer);
            }
        }
    }

    if (count == numCourses)
        return order;

    return new int[0];
}

        public List<String> anagrams(String[] strs) {

    //transfer the strings in the string list to stringarray,then sort them,
    // if there anagrams ,they will be the same
    // Use hashmap to store those words, use the sorted array as the key.
    // print all the List which size > 2 ====> result

    List<String> result = new ArrayList<String>();

     if (strs == null || strs.length == 0) {
        return result;
    }


    HashMap<String, ArrayList<String>> map = new HashMap<>();
    for(String temp : strs){
        char[] array = temp.toCharArray();
        Arrays.sort(array);
        String s = String.valueOf(array);
        ArrayList<String> list = map.getOrDefault(s, new ArrayList<>());
        list.add(temp);
        map.put(s, list);

    }

    for(Map.Entry<String, ArrayList<String>> entry : map.entrySet()){
        if(entry.getValue().size() > 1){
            result.addAll(entry.getValue());
        }
    }


    return  result;
}  

    public boolean validTree(int n, int[][] edges) {
    // Write your code here
    if(edges == null){
        return false;
    }

    //Notice !!!!
    if(edges.length != n - 1){
        return false;
    }

    Map<Integer, Set<Integer>> graph = graphinitial(n , edges);

    Queue<Integer> queue = new LinkedList<>();
    Set<Integer> set = new HashSet<>();

    queue.offer(0);
    set.add(0);

    while (!queue.isEmpty()){
        int node =  queue.poll();
        //注意这里是neighbor 不是node啊！
        for (Integer neighber : graph.get(node)){
            if (set.contains(neighber)){
                continue;
            }
            set.add(neighber);
            queue.offer(neighber);
        }
    }

    return (set.size() == n);

}


public Map<Integer, Set<Integer>> graphinitial(int n , int[][]edges){

    Map<Integer,Set<Integer>> graph = new HashMap<>();

    for (int i = 0; i < n;i++){
        graph.put(i, new HashSet<Integer>());
    }

    for (int i = 0; i < edges.length; i++){
        int u = edges[i][0];
        int v = edges[i][1];
        graph.get(u).add(v);
        graph.get(v).add(u);
    }
    return graph;
}

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    for (char c : s.toCharArray()) {
        if (c == '(')
            stack.push(')');
        else if (c == '{')
            stack.push('}');
        else if (c == '[')
            stack.push(']');
        else if (stack.isEmpty() || stack.pop() != c)
            return false;
    }
    return stack.isEmpty();
} 

public List<String> removeInvalidParentheses(String s) {
    int rmL = 0, rmR = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            rmL++;
        } else if (s.charAt(i) == ')') {
            if (rmL != 0) {
                rmL–;
            } else {
                rmR++;
            }
        }
    }
    Set<String> res = new HashSet<>();
    dfs(s, 0, res, new StringBuilder(), rmL, rmR, 0);
    return new ArrayList<String>(res);
}

public void dfs(String s, int i, Set<String> res, StringBuilder sb, int rmL, int rmR, int open) {
    if (rmL < 0 || rmR < 0 || open < 0) {
        return;
    }
    if (i == s.length()) {
        if (rmL == 0 && rmR == 0 && open == 0) {
            res.add(sb.toString());
        }
        return;
    }

    char c = s.charAt(i);
    int len = sb.length();

    if (c == '(') {
        dfs(s, i + 1, res, sb, rmL - 1, rmR, open);         // not use (
        dfs(s, i + 1, res, sb.append(c), rmL, rmR, open + 1);       // use (

    } else if (c == ')') {
        dfs(s, i + 1, res, sb, rmL, rmR - 1, open);             // not use  )
        dfs(s, i + 1, res, sb.append(c), rmL, rmR, open - 1);       // use )

    } else {
        dfs(s, i + 1, res, sb.append(c), rmL, rmR, open);
    }

    sb.setLength(len);
} 

      public String minWindow(String s, String t) {
    if(t.length()> s.length()) return "";
    Map<Character, Integer> map = new HashMap<>();
    for(char c : t.toCharArray()){
        if( map.containsKey(c)){
            map.put(c, map.get(c) + 1);
        }else{
            map.put(c,1);
        }
    }
    int counter = map.size();
    int begin = 0, end = 0;
    int head = 0;
    int len = Integer.MAX_VALUE;

    while(end < s.length()){
        char c = s.charAt(end);
        if( map.containsKey(c) ){
            map.put(c, map.get(c)-1);
            if(map.get(c) == 0) counter–;
        }
        end++;

        while(counter == 0){
            char tempc = s.charAt(begin);
            if(map.containsKey(tempc)){
                map.put(tempc, map.get(tempc) + 1);
                if(map.get(tempc) > 0){
                    counter++;
                }
            }
            if(end-begin < len){
                len = end - begin;
                head = begin;
            }
            begin++;
        }

    }
    if(len == Integer.MAX_VALUE) return "";
    return s.substring(head, head+len);
}

        public List<Interval> merge(List<Interval> intervals) {
    // write your code here
    List<Interval> ans = new ArrayList<>();

    intervals.sort(Comparator.comparing(i -> i.start));  //lambda 匿名函数：输入i  返回i.start

    Interval last = null;
    for (Interval item : intervals) {
        if (last == null || last.end < item.start) {
            ans.add(item);
            last = item;
        } else {
            last.end = Math.max(last.end, item.end); // Modify the element already in list
        }
    }
    return ans;
}

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    // write your code here
    List<Interval> ans = new ArrayList<>();

    int idx = 0;
    while (idx < intervals.size() && intervals.get(idx).start < newInterval.start) {
        idx++;
    }
    intervals.add(idx, newInterval);

    Interval last = null;
    for (Interval item : intervals) {
        if (last == null || last.end < item.start) {
            ans.add(item);
            last = item;
        } else {
            last.end = Math.max(last.end, item.end); // Modify the element already in list
        }
    }
    return ans;
}   

    public int longestConsecutive(int[] num) {
    // write you code here
    HashSet<Integer> set = new HashSet<>();
    for(int i = 0 ; i< num.length; i++){
        set.add(num[i]);
    }

    int max = 0;
    for(int i = 0; i < num.length; i++){
        int  down = num[i] - 1;
        while(set.contains(down)){
            set.remove(down);
            down–;
        }

        int up = num[i] + 1;
        while(set.contains(up)){
            set.remove(up);
            up++;
        }
        //为什么可以直接用up - down ? 因为是连续数
        max = Math.max(max, up - down - 1);
    }
    return max;
}